//************************************************************
//    > File Name: majority-number.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月21日 11:37:11
//***********************************************************
//lintcode #46
#include<bits/stdc++.h>
using namespace std;
int majorityNumber(vector<int> nums) {
	// write your code here
	int a=-1, c=0;
	for(int i=0; i<nums.size(); ++i){
		if (c==0){
			a = nums[i];
			c = 1;
		}
		else c += (a==nums[i] ? 1:-1);
	}
	return a;
}
int main(){
	vector<int> a={
		2,1,1,1,1,1,3,4,4
	};
	int res=majorityNumber(a);
	cout<<res<<endl;
}
